package zuo.algo.c06;

import zuo.algo.data.LinkedNode;
import zuo.algo.util.LinkedUtils;

import java.util.HashSet;
import java.util.Set;

/**
 * 00:04-获取链表第一个入环节点
 */
public class FindRingFirstNode {

    public static LinkedNode getNode1(LinkedNode head) {
        Set<LinkedNode> set = new HashSet<>();
        LinkedNode node = head;
        while (node != null) {
            if (set.contains(node)) {
                return node;
            }
            set.add(node);
            node = node.next;
        }
        return null;
    }

    /**
     * 快指针一次走两步，慢指针一次走一步
     * 如果有环的话快慢指针一定会相遇
     * 相遇后快指针从头开始每次走一步，慢指针从相遇节点每次走一步，它们必将在入环节点再次相遇
     */
    public static LinkedNode getNode2(LinkedNode head) {
        LinkedNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast != slow) {
            return null;
        }
        fast = head;
        while (fast != null) {
            if (fast == slow) {
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return null;
    }

    public static void main(String[] args) {
        LinkedNode head = LinkedUtils.constructLinkedList(new int[]{1, 2, 3, 4, 5, 6, 7});
        head.next.next.next.next.next.next.next = head.next.next.next;
        LinkedNode node1 = getNode1(head);
        LinkedNode node2 = getNode2(head);
        System.out.println();
    }
}
